package xiaohui;

import java.util.Arrays;
import java.util.PriorityQueue;

public class TwoHeapTest {
    public static void main(String[] args) {
        PriorityQueue queue = new PriorityQueue(Arrays.asList(7, 1, 3, 10, 5, 2, 8, 9, 6));
//        int[] array = new int[]{1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
//        upAdjust(array);
//        //插入0节点上浮
//        System.out.println(Arrays.toString(array));
//        array = new int[]{7, 1, 3, 10, 5, 2, 8, 9, 6};
//        buildHeap(array);
//        System.out.println(Arrays.toString(array));
    }

    public static void upAdjust(int[] array) {
        int childIndex = array.length - 1;
        int parentIndex = (childIndex - 1) / 2;
        int temp = array[childIndex];
        while (childIndex > 0 && temp < array[parentIndex]) {
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = temp;
    }

    public static void downAdjust(int[] array, int parentIndex) {
        int childIndex = parentIndex * 2 + 1;
        int temp = array[parentIndex];
        while (childIndex < array.length) {
            int rightChildIndex = childIndex + 1;
            if (rightChildIndex < array.length && array[rightChildIndex] < array[childIndex]) {
                childIndex++;
            }
            if (temp <= array[childIndex]) {
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = childIndex * 2 + 1;
        }
        array[parentIndex] = temp;
    }

    public static void buildHeap(int[] array) {
        // 从最后一个非叶子节点开始，依次做“下沉”调整
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            downAdjust(array, i);
        }
    }
}
